import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2024/5/27 19:19
 * @description: 力扣39
 * .    https://leetcode.cn/problems/combination-sum/// 字节谷歌亚马逊, dfs.  组合总和II 还有3 4和这个差不多, 都是同一种类型
 * @Author LittleNight
 */
public class likou39 {

    List<List<Integer>> ret;
    List<Integer> path;
    int sum, target1;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        sum = 0; target1 = target;

        dfs(candidates, 0);
        return ret;
    }

    private void dfs(int[] candidates, int pos) {
        if(sum == target1) {
            ret.add(new ArrayList<>(path));
            return;
        }
        // 在这里进行判断
        if(sum > target1 || pos == candidates.length) return;
        // 主逻辑, 遍历 pos 位置及以后的节点
        for (int i = pos; i < candidates.length; i++) {
            sum += candidates[i];
            path.add(candidates[i]);
            dfs(candidates, i + 1); // 递归下一层, 是从 i 开始, 因为 i 会变化
            // 进行一步剪枝操作, 如果已经超过目标和了, 就直接返回, 否则, 就继续遍历. 因为是2 3 5是越来越大的
            // 如果当前已经不满足了, 在回溯遍历后面的更不满足
            // 回溯, 恢复现场
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}
